#include "Dwarf.Unmanaged.Omp.h"


Solver :: Solver()
{

}

Solver :: ~Solver()
{    

}
//For the demonstration purposes of the project,
//we have chosen depth first search algorithm
void Solver::solve() 
{   
    int numberOfThread;
    #pragma omp parallel 
    {
        numberOfThread = omp_get_num_threads();
    }
    bool *finishArray = new bool[numberOfThread];
    for(int i = 0; i <numberOfThread;i++)
    {
        finishArray[i] = false;
    }
    stack<int> s;
    //set the head of graph
    int headId = graph->getHeadId();
    graph->setVisited(headId);
    s.push(headId);
    int finish = false;
    #pragma omp parallel 
    {
        //while deque not empty
        deque<int> d;
        #pragma omp master
        {
            d.push_front(s.top());
            s.pop();
        }
        int u;
        //while all threads is not finishing.
        while (!finish) 
        {
            if(!d.empty()) 
            {
                //take the first element
                u = d.front();
                //for all edges of current vertex
                bool hasNoVisited = true;
				// NOTE: If edges aren't unique, then the following is not correct.
				//       In that case, getVisited/setVisited should be atomic.
                for(int j = 0; j < graph->arrayOfcounts[u]; j++)
                {
                    int count =  graph->getVisited(graph->edgesMatrix[u][j]);
                    if(count == 0) 
                    {
                        //adding new vertex to work stack
                        hasNoVisited = false;
						#pragma omp critical
						{
                        	d.push_front(graph->edgesMatrix[u][j]);
						}
                        graph->setVisited(graph->edgesMatrix[u][j]);
                        break;
                    }
                }
                //if has no visited then delete element from deque
                if(hasNoVisited)
                {   
                    d.pop_front();
                }
                if ( s.size() < 1 && d.size() > 1)
                {   
                    #pragma omp critical
                    {
                        s.push(d.back());
                        d.pop_back();
                    }
                }
            }
            else 
            {
                //critical section, set the new tasks
                #pragma omp critical
                {
                    if(!s.empty())
                    {
                        d.push_front(s.top());
                        s.pop();
                        finishArray[omp_get_thread_num()] = false;
                    } 
                    else
                    {
                        finishArray[omp_get_thread_num()] = true;
                    }
                }
            }
            //check the end of work
            #pragma omp master
            {
                bool tempFinish = true;
                for(int i = 0; i < numberOfThread; i++)
                {
                    if (!finishArray[i])
                    {
                        tempFinish = false;
                        break;
                    }
                }
                finish = tempFinish;
            }
        }
    }
}


